package com.lm.leetcode.briefsummary;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Auther: Min.Liu
 * @Description: 一、 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
 * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
 * <p>
 * 二、给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
 * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
 * <p>
 * 三、对于问题二 能否优化你的算法到 O(rowIndex) 空间复杂度？
 * @Date: Created in 11:37 2025/5/12
 */
public class GenerateDemo {
    public static void main(String[] args) {
        GenerateDemo demo = new GenerateDemo();
        System.out.println(demo.generate3(4));
    }

    public List<List<Integer>> generate1(int numRows) {
        LinkedList list = new LinkedList<LinkedList<Integer>>();
        for (int i = 1; i <= numRows; i++) {
            creatRow(list, i);
        }
        return list;
    }

    private void creatRow(LinkedList<LinkedList<Integer>> list, int i) {
        LinkedList newlist = new LinkedList<Integer>();
        if (i == 1) {
            newlist.add(1);
            list.add(newlist);
            return;
        }
        if (i == 2) {
            newlist.add(1);
            newlist.add(1);
            list.add(newlist);
            return;
        }

        LinkedList<Integer> oldlist = list.get(i - 2);
        newlist.add(1);
        int start = 0;
        while (start < i - 2) {
            newlist.add(oldlist.get(start) + oldlist.get(start + 1));
            start++;
        }
        newlist.add(1);
        list.add(newlist);
    }

    public List<Integer> generate2(int numRows) {
        LinkedList<LinkedList<Integer>> list = new LinkedList<>();
        for (int i = 1; i <= numRows + 1; i++) {
            creatRow(list, i);
        }
        return list.get(numRows);
    }

    //空间复杂度优化
    public List<Integer> generate3(int numRows) {
        ArrayList<Integer> list = new ArrayList(numRows+1);
        for (int i = 0; i <= numRows; i++) {
            list.add(1);
        }
        if (numRows == 0 || numRows == 1){
            return list;
        }
        for (int i = 2; i <= numRows; i++) {
            int start = i-1;
            while (start>0) {
                list.set(start,list.get(start-1)+list.get(start));
                start--;
            }
        }
        return list;
    }



}
